package org.lql.algo.codecrush.hot100.dynamicProgramming;

import java.util.Arrays;

/**
 * @author: liangqinglong
 * @date: 2025-09-13 22:19
 * @description: 300. 最长递增子序列 <a href="https://leetcode.cn/problems/longest-increasing-subsequence/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 **/
public class LengthOfLIS {

	public int lengthOfLIS(int[] nums) {
		int n = nums.length;
		int[] dp = new int[n];
		Arrays.fill(dp, 1);
		for (int i = 1; i < n; i++) {
			for (int j = 0; j < i; j++) {
				if (nums[i] > nums[j]) {
					dp[i] = Math.max(dp[i], dp[j] + 1);
				}
			}
		}
		int ans = 0;
		for (int j : dp) {
			ans = Math.max(ans, j);
		}
		return ans;
	}
}
